package 代码随想录_动态规划.完全背包;

/**
 * @author zx
 * @create 2022-05-31 16:57
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i]：和为i的完全平方数的最少数量为dp[i]
 * 2.确定递推公式
 *   dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
 *   此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
 * 3.dp数组如何初始化
 *  dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。
 *  从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);
 *  中可以看出每次dp[j]都要选最小的，所以非0下标的dp[i]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
 * 4.确定遍历顺序
 *  所以本题并不强调集合是组合还是排列。
 *  *  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *  *  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 *  *  所以采用本人(zx)喜欢的方式：(物品)放在外循环,(背包)在内循环.且内循环正序.
 * 5.举例推导dp数组
 *
 */
public class 完全平方数_279 {
    /**
     * @return 背
     */
    public int numSquares(int n) {
        //dp[i]：和为i的完全平方数的最少数量为dp[i]
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int i = 1;i < dp.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 1;i * i <= n;i++){//物品
            for(int j = 1;j <= n;j++){//背包
                if(j - i * i >= 0 && dp[j - i * i] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
                }
            }
        }
        return dp[n];
    }
}
